package Leetcode.数组字符串;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * @ClassName 数组中的第K个最大元素
 * @since: 2023/8/23 08:43
 * @auth: kirito
 * @description:
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4], k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6], k = 4
 * 输出: 4
 **/
public class 数组中的第K个最大元素 {
    private final static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int target = len - k; // 要找的是第 k 大的数，对应的下标是 len - k

        int left = 0;
        int right = len - 1;

        while (true) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == target) {
                return nums[pivotIndex]; // 当找到第 k 大的数时，直接返回
            } else if (pivotIndex < target) {
                left = pivotIndex + 1; // 当前分区的右边部分包含的元素多于 k，往右侧继续查找
            } else {
                right = pivotIndex - 1; // 当前分区的右边部分包含的元素少于 k，往左侧继续查找
            }
        }
    }

    //快排思想
    private int partition(int[] nums, int left, int right) {
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randomIndex); // 将随机选择的元素与左边界元素交换，作为分区的基准元素

        int pivot = nums[left];
        int le = left + 1; // 左指针，指向分区中小于基准元素的最后一个位置的下一个位置
        int ge = right; // 右指针，指向分区中大于基准元素的第一个位置

        while (true) {
            while (le <= ge && nums[le] < pivot) {
                le++; // 左指针向右移动，直到找到大于等于基准元素的位置
            }

            while (le <= ge && nums[ge] > pivot) {
                ge--; // 右指针向左移动，直到找到小于等于基准元素的位置
            }

            if (le >= ge) {
                break; // 左指针和右指针相遇，分区结束
            }
            swap(nums, le, ge); // 交换左指针和右指针所指向的元素
            le++;
            ge--;
        }

        swap(nums, left, ge); // 将基准元素放到正确的位置
        return ge; // 返回基准元素的下标
    }
    //堆排序   第K大元素就是删除k-1次后堆顶的元素
    public int findKthLargest2(int[] nums, int k) {
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        /*
        从 heapSize / 2 开始遍历是为了确保只对非叶子节点进行 maxHeapify 操作。
        叶子节点自身已经是一个最大堆（因为它没有子节点），所以不需要对其进行 maxHeapify 操作。
        从 heapSize / 2 开始向前遍历，可以保证从最后一个非叶子节点开始，依次向上调整每个子树，
        使得每个子树都满足最大堆性质。这是因为最后一个非叶子节点之后的节点都是叶子节点，
        它们自身已经满足最大堆性质。
         */
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        //堆性质  左子节点和右子节点
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        /*
        l < heapSize的判断条件是用来检查左子节点的索引是否在堆的范围内。
        heapSize表示堆的大小，即堆中实际包含的元素数量。如果左子节点的索引超过了堆的大小，
        说明该节点不存在，因为堆是完全二叉树，不会存在只有右子节点而没有左子节点的情况。
        如果左子节点的索引超过了堆的大小，那么该节点显然不可能是最大堆的一部分，
        因此不需要对其进行比较和交换操作。
         */
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            //只是数组的两个位置的值交换了，但是largest的索引还是子树的位置
            //所以需要继续构建，类比于向下构建堆（画图跑一边就知道了。。）
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    //交换数组两个索引的位置
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
